package sort;

import org.jetbrains.annotations.NotNull;

import java.util.HashMap;
import java.util.Map;

/**
 * @author dx
 * @version 1.0
 * @date 2022/3/21 22:12
 * @description:给定一个大小为n的数组，找到其中的多数元素，
 * 多数元素是指在数组中出现次数大于[n/2]的元素
 *
 */
public class find_duoshu {
    public static void main(String []args){
        int a[] = {1,1,1,2,2,2,2,2,2,3,4,4,4,4,5,5,5,5,5};
       int majority = find_duoshu(a);
       System.out.println(majority);
    }


    //将数组中的元素按照 value:次数  的方式存入Map
    private static Map<Integer,Integer> countNums(int nums []){

        int len = nums.length;
        Map<Integer,Integer> counts = new HashMap<Integer,Integer>();
        for(int num : nums){
            if(!counts.containsKey(num)){
                counts.put(num,1);
            }else {
                counts.put(num,counts.get(num)+1);
            }
        }
        return counts;
    }
    //查询Map中的大数
    public static int find_duoshu(int nums[]){

        Map<Integer,Integer> counts = countNums(nums);
        Map.Entry<Integer,Integer> Majority = null;
        for(Map.Entry<Integer,Integer> entry : counts.entrySet()){
            if(Majority == null || entry.getValue()>Majority.getValue()){
                Majority = entry;
            }
        }
        return Majority.getKey();
    }
}
